# -*- coding:utf-8 -*-

# author: firstoneyuan
# email: devops_yj@163.com

# 求100内的素数

# 一个数能被从2开始到自己的平方根的正整数整数整除,就是合数.
import math
n = 100
for x in range(2,n):
    for i in range(2,math.ceil(math.sqrt(x))):
        if x % i == 0:
            break
    else:
        print(x)

# 改进1
# 存储质数合数一定可以分解为几个质数的乘积
import math
n = 100
primenumber = []
for x in range(2,n):
    for i in primenumber:
        if x % i == 0:
            break
    else:
        print(x)
        primenumber.append(x)

# 改进2
# 使用列表存储已有的质数,同时增加范围
import math 
primenumber = []
flag = False
for x in range(2,1000):
    for i in primenumber:
        if x % i == 0:
            flag = True
            break
        if i >= math.ceil(math.sqrt(x)):
            flag = False
            break
    if not flag:
        print(x)
        primenumber.append(x)


import datetime

upper_limit = 10000

start = datetime.datetime.now()
count = 1
for x in range(3,upper_limit,2): #舍弃掉所有偶数.
    if x > 10 and x % 10 == 5: #所有大于10的质数中,个位数只有1,3,7,9,意思就是大于5,结尾是5就能被5整除了.
        continue
    for i in range(3,int(x ** 0.5) + 1,2): # 为什么从3开始,且step为2?
        if x % i == 0:
            break
    else:
        count += 1
        # print(x,count)
        pass

delta = (datetime.datetime.now() - start).total_seconds()
print(delta)
print(count)
print("~~~~~~~~~~~~~~~~~~~~")

start = datetime.datetime.now()
x = 5
step = 2
count = 2
#print(2,3,sep='\n')
while x < upper_limit:
    for i in range(3,int(x**0.5) + 1,2): #p和n都是奇数,那么不必和偶数整除.
        if not x % i:
            break
    else:
        #print(x)
        count += 1
    
    x += step
    step = 4 if step == 2 else 2


delta = (datetime.datetime.now() - start).total_seconds()
print(delta)
print(count)

print("~~~~~~~~~~~")




# 改进2
# 使用列表存储已有的质数,同时增加范围
import math

start = datetime.datetime.now()
primenumber = []
flag = False
count = 0
for x in range(2,10000):
    for i in primenumber:
        if x % i == 0:
            flag = True
            break
        if i >= math.ceil(math.sqrt(x)):
            flag = False
            break
    if not flag:
        # print(x)
        count += 1
        primenumber.append(x)

delta = (datetime.datetime.now() - start).total_seconds()
print(delta)
print(count)

print("~~~~~~~~~")



# 改进2
# 使用列表存储已有的质数,同时增加范围
import math

start = datetime.datetime.now()
primenumber = []
flag = False
count = 1
for x in range(3,10000,2): #奇数
    for i in primenumber:
        if x % i == 0:
            flag = True
            break
        if i >= math.ceil(math.sqrt(x)):
            flag = False
            break
    if not flag:
        # print(x)
        count += 1
        primenumber.append(x)

delta = (datetime.datetime.now()- start).total_seconds()
print(delta)
print(count)
print("~~~~~~~~~")


# 改进2
# 使用列表存储已有的质数,同时缩小取模范围.
import math 

start = datetime.datetime.now()
flag = False
count = 1
for x in range(3,1000,2):
    edge = math.ceil(math.sqrt(x))
    for i in primenumber:
        if x % i == 0:
            flag = True
            break
        if i >= edge:
            flag = False
            break
    if not flag:
        # print(x)
        count += 1
        primenumber.append(x)

delta = (datetime.datetime.now() - start).total_seconds()
print(delta)
print(count)
print("~~~~~~~")

"""
直接提速,计算速度第一位
本质上就是空间换时间.
"""